2.5D IC is a packaging technique for connecting multiple dies to each other or to an external circuitry. A 2.5-dimensional integrated circuit (2.5D IC), which introduces an interposer as an interface between chips and a package, is one of the most popular integration technologies. Multiple chips can be mounted on an interposer, and inter-chip nets are routed on redistribution layers (RDLs). Redistribution layers (RDLs) are used to route nets between dice, dice and package substrate. In traditional designs, the wire widths and spacings are uniform (i.e., grid-based). To improve circuit performance in modern designs, however, variable widths and spacings are also often adopted (i.e., gridless designs).
Recently, 2.5-dimensional integrated circuits (2.5D ICs, also known as interposer-based 3D ICs) have become one of the most popular packaging technologies which support heterogeneous integration and enhance system performance while reducing power consumption and manufacturing complexity. With multiple chips mounted on the interposer, inter-chip nets can be routed on redistribution layers (RDLs) of the interposer by using the same processes as the silicon chips. The integrated chips may come from different vendors, which introduce predefined connections, i.e., pre-assignment nets. Moreover, different from stacked 3D IC packages which employ through-silicon vias (TSVs) to communicate between different layers and the substrate, a 2.5D IC package contains TSVs only in their interposers. Due to the lower fabrication cost and design complexity, many vendors, including ASE, eSilicon, and GlobalFoundries, have adopted 2.5D IC packages as their next-generation solutions for various applications.
In order to improve circuit performance, some optimization techniques, including wire sizing and wire spacing, are proposed to meet the timing and/or power constraints. However, routing complexity increases dramatically due to the variable widths and spacings.
FIG. 1a shows the side view of a 2.5D IC package structure. The main feature of a 2.5D IC package is the interposer 116 which is introduced as an interface between chips 100, 102 and a package (substrate) 122. FIG. 1a shows a general 2.5D IC package, which contains an interposer 116 with inter-chip nets 104 routed on RDLs 112. The through-silicon vias (TSVs) 114 is used to communicate between different layers and the package substrate 122 via frontside bumps 110, frontside RDLs 112, backside RDLs 118 and backside bumps 120. Traditional RDL routing algorithms can be divided into two categories: (1) mathematical programming and (2) graph-based methods. For mathematical programming, Fang et al. proposed an integer linear programming (ILP) based formulation which completes global routing with several reduction techniques to prune redundant solutions (please refer to: J.-W. Fang, C.-H. Hsu, and Y.-W. Chang. An integer-linear-programming based routing algorithm for flip-chip designs. In IEEE TCAD, volume 28, pages 98-110, January 2009). Though this formulation can often obtain the optimal wirelength for global routing, the high time complexity of an ILP makes it prohibitive for solving large-scale designs. For graph-based methods, the previous works adopted network-flow-based methods to deal with RDL routing. Liu et al. exploited the geometrical properties of Voronoi diagrams to model global-routing channels and applied a network flow-based algorithm to solve the routing problem (please refer to: X. Liu, Y. Zhang, G. K. Yeap, C. Chu, J. Sun, and X. Zeng. Global routing and track assignment for flip-chip designs. In Proc. of ACM/IEEE DAC, pages 90-93, June 2010). Based on network-flow-based formulations, flip-chip routing was handled by Fang et al. (please refer to: J.-W. Fang, I.-J. Lin, Y.-W. Chang, and J.-H. Wang. A network-flow-based RDL routing algorithm for flip-chip design. In IEEE TCAD, volume 26, pages 1417-1429, August 2007) and also package-board co-design by Fang et al. (please refer to: J.-W. Fang, M. D. F. Wong, and Y.-W. Chang. Flip-chip routing with unified area-i/o pad assignments for package-board co-design. In Proc. of ACM/IEEE DAC, pages 336-339, July 2009). However, they cannot directly apply to designs with variable wire widths and spacings.
Moreover, a typical structure of the 2.5D IC package, connecting multiple bump pairs on different chips often involves long and parallel inter-chip nets, as shown in FIG. 1b. The long and parallel inter-chip nets may induce severe coupling effects between signals, which degrades signal integrity and circuit performance. In the work of Chen et al. (please refer to: T.-C. Chen, Y.-W. Chang, and S.-C. Lin. A novel framework for multilevel full-chip gridless routing. In Proc. of IEEE/ACM ASP-DAC, pages 636-641, January 2006), a V-shaped multilevel framework was proposed for full-chip gridless routing. This method first partitions a layout into an array of rectangular subregions, and then routes wires of different widths sequentially on those subregions. Without considering routing resources and net ordering, however, it may cause a detour when the routing resource has been occupied by other routed wires.
To better handle the routing problem on RDLs with various constraints, traditional combinatorial routing algorithms might not be sufficient for solving the problem effectively. Therefore, the invention proposes a unified RDL routing framework to resolve the above-mentioned problems.